package datastruct;

import java.util.Stack;

public class ImplementQueueUsingStacks232 {
    class MyQueue {
        // 正序的stack, top最新, 用于push
        Stack<Integer> queuedStack = new Stack<>();

        // 逆序的stack, top最旧, 用于pop
        Stack<Integer> reversedStack = new Stack<>();

        public MyQueue() {
        }

        public void push(int x) {
            while (!reversedStack.isEmpty()) {
                queuedStack.push(reversedStack.pop());
            }
            queuedStack.push(x);
        }

        public int pop() {
            while (!queuedStack.isEmpty()) {
                reversedStack.push(queuedStack.pop());
            }
            if (reversedStack.isEmpty()) {
                return Integer.MIN_VALUE;
            }
            return reversedStack.pop();
        }

        public int peek() {
            while (!queuedStack.isEmpty()) {
                reversedStack.push(queuedStack.pop());
            }
            if (reversedStack.isEmpty()) {
                return Integer.MIN_VALUE;
            }
            return reversedStack.peek();
        }

        public boolean empty() {
            return queuedStack.isEmpty() && reversedStack.isEmpty();
        }
    }
}
